186 HISTORY OF THE THEOEY OF NUMBERS. [CHAP. VII
To find a primitive root g of p, select any convenient integer a and form the residues of a, a2, a3, . . . [as by Crelle18]. Let n be the exponent to which a belongs. Set nri — p — 1. If n<p — 1, select an integer b not in the period a, . . . , an. The residue of bn' is in this period of a. If bf is the least power of b whose residue is in the period of a, then / divides n'} say n'=ff' (p- xxiii). Since a=gn', bf^a\ we have
b'=g*'^gff'i+nff'k, b=gf/(i+n» (mod p),
for some value 0, 1, . . ., /— 1 of fc. But fc must be chosen so that i+wfc is prime to /. For, if i+nk = du, where d is a divisor of /, we would have b//d==au. The nf residues of arb3 (r = 0,. . ., n-1; s = 0,. . ., /-I) are distinct ; then- indices to base g are/', 2/', . . . , n//' hi some order and are known. If nf'<p — l, we employ an integer not in the set arbs and proceed similarly. Ultimately we obtain a primitive root and at the same time the index of every number. This method was used for the primes between 200 and 1000.
For primes < 200, the tables by Ostrogradsky22 were reprinted with the same errors (noted at the end of the Canon).
Jacobi proved that, if n is an odd prime, any primitive root of n2 is a primitive root of any higher power of n (p. xxxv).
For the modulus 2", 4^/-t^9, the final tables give the index 7 of any positive odd number to base 3, where
Robert Murphy24 stated the empirical theorem that every prime an2 -hp has a as a primitive root if p>a/2, p is a prime <a, and if a is a primitive root of p. For example, a prime 10n2+7 has 10 as a primitive root.
H. G. Erlerus25 considered two odd primes p and p' and a number m such that w = a (mod p), ra = a' (mod p'). Let a belong to the exponent e modulo p, and a' to the exponent e' modulo p'. If 8 is the g. c. d. of e and e' ', then m belongs to the exponent ee'/d modulo pp'. He discussed at length the number of integers belonging to the exponent n for a composite modulus.
A. Cauchy26 called the least positive integer i for which m* = l (mod n) the indicator relative (or corresponding) to the base m and modulus n, which are assumed relatively prime. If the base m is constant, and ilt i2 are the indicators corresponding to moduli nlt n2) and if n — nln2 is prime to m, then the 1. c. m. of ^ and i2 is the indicator corresponding to modulus n. If the modulus n is constant, and ii , i2 are the indicators corresponding to bases ml, m2} and if i1} i2 are relatively prime, then ifo is the indicator corresponding to the base Wim2.
Let ij, i2 be the indicators corresponding to the bases mi, m2 and same modulus n. The g. c. d. co of ilt i2 can be expressed (often in several ways) as a product uv such that i\/u^ i$/v are relatively prime. For, if to — a/3. . . ,
"Phil. Mag., (3), 19, 1841, 369.
^Elementa Doctrinae Numerorum, Diss., Halis, 1841, 18-43.
"Cornptes Rendus Paris, 12, 1841, 824-845; Oeuvres, (1), 6, 124-146.